package 动态规划;

public class 数字转字符串 {

    public static void main(String[] args) {

        String s = "111";
        System.out.println(number(s));
    }

    public static int number(String str) {
        //终止条件
        if (str == null) return 0;
        if (str.length() == 1) return 1;
        System.out.println(helper(str.toCharArray(), 0));
        return help(str.toCharArray(), 0);
    }

    private static int helper(char[] str, int i) {
        int N = str.length;//得到原数组的长度
        //创建状态容器
        int[] dp =new int[N+1];
        dp[N] = 1;
        for (int j = N-1; j >= 0; j--) {
            if (str[j] != '0'){
                int ways = dp[j+1];
                if(j+1 < str.length && (str[j] - '0') * 10 + (str[j+1] - '0') < 27){
                    ways += dp[j+2];
                }
                dp[j] = ways;
            }
        }
        return dp[0];
    }


    /**
     * 递归
     * 传输一个数组和当前位置，我就可以返回有多少种组合的方法
     * @param arr
     * @param i
     * @return
     */
        private static int help(char[] arr,int i){
            //终止条件
            if (i >= arr.length) {
                return 1;
            }
            //305时，0无法对应任何数，决策有误，返回0；
            if (arr[i] == '0') {
                return 0;
            }
            //否则至少存在两个，因为A~Z分别对应1~26，所以需要传入的数字一次可以走一步，或者走两部
            //我只知道当前的，可以走一步或者走两步
            //无论我在什么位置，我都有继续向前一步的策略
            int p1 = help(arr, i + 1);
            int p2 = 0;
            //向前两部的策略是，我在当前位置，我的下一个位置有元素，并且i和i+1组成的数字必须小于27，那么向前两部的策略才正确，否则策略失败
            if (i + 1 < arr.length && (arr[i] - '0') * 10 + (arr[i + 1]) - '0' < 27) {
                p2 = help(arr, i + 2);
            }
            //最终返回向前一步和两部的策略和
            return p1 + p2;
        }
}

